#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0] = costs[0];
        for (int i = 1; i < n; ++i)
        {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
            dp[i][1] = min(dp[i - 1][2], dp[i - 1][0]) + costs[i][1];
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + costs[i][2];
        }
        return min(dp[n - 1][0], min(dp[n - 1][1], dp[n - 1][2]));
    }

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; ++i)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][2], dp[i - 1][1]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2]));
    }

    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = -prices[0] - fee;
        for (int i = 1; i < n; ++i)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i] - fee);
            dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }
        return dp[n - 1][1];
    }

    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n, vector<int>(3, -0x3f3f3f3f));
        auto g = f;
        f[0][0] = -prices[0], g[0][0] = 0;
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j < 3; ++j)
            {
                f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);
                g[i][j] = g[i - 1][j];
                if (j >= 1) g[i][j] = max(f[i - 1][j - 1] + prices[i], g[i][j]);
            }
        }
        return max(g[n - 1][0], max(g[n - 1][1], g[n - 1][2]));
    }

    int minSpeedOnTime(vector<int>& dist, double hour) {
        int n = dist.size();
        long long hr = llround(hour * 100);
        if ((n - 1) * 100 >= hr) return -1;
        int left = 1, right = 1e7;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            long long t = 0;
            for (int i = 0; i < n - 1; ++i)
            {
                t += (dist[i] - 1) / mid + 1;
            }
            t *= mid;
            t += dist[n - 1];
            if (t * 100 <= hr * mid) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};